#pragma once
#include <map>
#include <limits>

using std::map;
using std::pair;
using std::make_pair; 

template <typename Name>
class BiGraph {  
  public:
    class Vertex;
    class Edge; 
    
    template <typename T, typename U>
    class Iterator{
      public:   
        Iterator(T It):ptr(It) {};
        Iterator& operator++(){ptr++; return *this;} 
        Iterator& operator--(){ptr--; return *this;} 
        Iterator operator++(int){Iterator temp; temp.ptr=ptr; ptr++; return temp;}
        Iterator operator--(int){Iterator temp; temp.ptr=ptr; ptr--; return temp;} 
        bool operator==(const Iterator& It) const {return (ptr==It.ptr);} 
        bool operator!=(const Iterator& It) const {return (ptr!=It.ptr);} 
        U& operator*(){ return *(ptr->second); } 
        U* operator->(){ return ptr->second; }
        Iterator& operator=(const Iterator& It) {ptr=It.ptr; return *this;} 
      private:
        T  ptr;
    };
    
    typedef typename map<Name,Vertex*>::iterator map_NV_It;
    typedef typename map<Vertex*, Edge*>::iterator map_VE_It;
    typedef Iterator< map_NV_It, Vertex > Vertex_Iterator;
    typedef Iterator< map_VE_It, Edge > In_Edge_Iterator;
    typedef Iterator< map_VE_It, Edge > Out_Edge_Iterator;
    
    typedef std::pair<Vertex_Iterator, Vertex_Iterator> Vertices_Range;
    
    class Edge{
        friend class BiGraph; 
      public:
        Edge(Vertex* start, Vertex* end, double w):weight(w), start_vertex(start), end_vertex(end) {}
        pair<Name, Name> get_name() const { return make_pair(start_vertex->get_name(), end_vertex->get_name()); }
        pair<Vertex*,Vertex*> get_vertices() const { return make_pair(start_vertex, end_vertex); }
        double get_weight() const { return weight; }
        
      private:
        double weight;
        Vertex* start_vertex;
        Vertex* end_vertex;
    };
    
    class Vertex{
        friend class BiGraph;  
      public:
        Vertex(const Name &_name): name(_name){}
        Name get_name() const { return name; }
        double cost;
        Vertex* parent;
        
        In_Edge_Iterator in_edge_begin() { return In_Edge_Iterator(in_edges.begin()); }
        In_Edge_Iterator in_edge_end() { return In_Edge_Iterator(in_edges.end()); }
        
        Out_Edge_Iterator out_edge_begin() { return Out_Edge_Iterator(out_edges.begin()); }
        Out_Edge_Iterator out_edge_end() { return Out_Edge_Iterator(out_edges.end()); }
      private:
        Name name;
        map<Vertex*, Edge*> out_edges;
        map<Vertex*, Edge*> in_edges;     
    };
    
    BiGraph():edges_count(0){}
    ~BiGraph(){ clear(); }
    void clear();
    
    Vertex_Iterator begin() { return Vertex_Iterator(vertices_map.begin()); }
    Vertex_Iterator end() { return Vertex_Iterator(vertices_map.end()); }
    
    pair<bool, Vertex*> add_vertex(const Name &v);
    Edge* add_edge(const Name &start,const Name & end, double weight);
    bool delete_edge(const Name& start,const Name& end);
    
    Vertices_Range vertices() const { return make_pair(begin(),end()); }
    
    size_t vertices_count() const { return vertices_map.size(); }
    size_t edge_count() const { return edges_count; }
    
    Vertex* get_vertex(const Name& n) { return vertices_map[n]; }
    Edge* get_edge(const Name& n1, const Name& n2) { return vertices_map[n1]->out_edges[vertices_map[n2]]; }
    
    Vertex* Bellman_Ford(Vertex* s);
    
  private:
    map<Name,Vertex*> vertices_map;
    size_t edges_count;
    
    Vertex* find_or_create_vertex(const Name &v);
    void relax(Edge* e);
    
};



template <typename T>
typename BiGraph<T>::Edge* BiGraph<T>::add_edge(const T &start,const T & end, double weight){
    if (start==end) { add_vertex(start); return 0;}
    
    Vertex* start_vertex = find_or_create_vertex(start);
    Vertex* end_vertex = find_or_create_vertex(end);
        
    map_VE_It existing_edge=start_vertex->out_edges.find(end_vertex);
        
    if ( existing_edge!=start_vertex->out_edges.end()){ return existing_edge->second; }
    Edge* new_edge = new Edge(start_vertex, end_vertex, weight);
    start_vertex->out_edges.insert(make_pair(end_vertex, new_edge));
    end_vertex->in_edges.insert(make_pair(start_vertex, new_edge));
        
    ++edges_count;
    return new_edge;
}

template <typename T>
bool BiGraph<T>::delete_edge(const T& start,const T& end){
    if (vertices_map.find(start)==vertices_map.end()) { return false; }
    if (vertices_map.find(end)==vertices_map.end()) { return false; }
        
    Vertex* start_vertex = vertices_map[start];
    Vertex* end_vertex = vertices_map[end];
    if ( start_vertex->out_edges.find(end_vertex)==start_vertex->out_edges.end()) { return false; }
    start_vertex->out_edges.erase(end_vertex);
    delete end_vertex->in_edges[start_vertex];
    end_vertex-> in_edges.erase(start_vertex);
        
    --edges_count;
    return true;
}

template <typename T>
pair<bool, typename BiGraph<T>::Vertex*> BiGraph<T>::add_vertex(const T &v){
    if ( vertices_map.find(v)!=vertices_map.end()){return make_pair(false, vertices_map[v]) ;}
    Vertex* y  = new Vertex(v);
    vertices_map.insert(make_pair(v, y));
         
    return make_pair(true, y);
} 

template <typename T>
void BiGraph<T>::clear(){
    for (map_NV_It i=vertices_map.begin(); i!=vertices_map.end();++i){
        for (Out_Edge_Iterator y = i->second->out_edge_begin(); y!=i->second->out_edge_end(); ++y) { delete &(*y); }
        delete i->second;
    }
    vertices_map.clear();
}

template <typename T>
typename BiGraph<T>::Vertex* BiGraph<T>::Bellman_Ford(Vertex* s){
    for( Vertex_Iterator i=begin(); i!= end(); ++i){
        i->cost=std::numeric_limits<double>::infinity();
        i->parent=NULL;
    }
    s->cost=0;
         
    for (size_t r=1; r<edge_count(); ++r){
        for( Vertex_Iterator i=begin(); i!= end(); ++i){
            for( Out_Edge_Iterator y = i->out_edge_begin(); y!=i->out_edge_end(); ++y){ relax(&(*y)); }
        }
    }
    
    for( Vertex_Iterator i=begin(); i!= end(); ++i){
        for( Out_Edge_Iterator y = i->out_edge_begin(); y!=i->out_edge_end(); ++y ){
            Vertex* u = y->get_vertices().first;
            Vertex* v = y->get_vertices().second;
            if ( (v->cost) > (u->cost + y->get_weight()) ) { return v; }
        }
    }
    return 0;
}

template <typename T>
typename BiGraph<T>::Vertex* BiGraph<T>::find_or_create_vertex(const T &v){
    if (vertices_map.find(v)==vertices_map.end()){
        Vertex* new_vertex = new Vertex(v);
        vertices_map.insert(make_pair(v, new_vertex));
        return new_vertex;
    }
    return vertices_map[v];
}

template <typename T>
void BiGraph<T>::relax(BiGraph<T>::Edge* e){
    Vertex* u = e->get_vertices().first;
    Vertex* v = e->get_vertices().second;
    if ( (v->cost) > (u->cost) + e->get_weight() ) {
        v->cost = u->cost + e->get_weight();
        v->parent = u;     
    }
}
